package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 3266. K 次乘运算后的最终数组 II
 * <p>
 * 给你一个整数数组 nums ，一个整数 k  和一个整数 multiplier 。
 * <p>
 * 你需要对 nums 执行 k 次操作，每次操作中：
 * <p>
 * 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
 * 将 x 替换为 x * multiplier 。
 * k 次操作以后，你需要将 nums 中每一个数值对 109 + 7 取余。
 * <p>
 * 请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。
 */
public class Leetcode3266 {


    public static void main(String[] args) {
        Leetcode3266 obj = new Leetcode3266();
        int[] nums = new int[]{1};
        int k = 1000000000;
        int multiplier = 1;
        int[] res = obj.getFinalState(nums, k, multiplier);
        System.out.println(Arrays.toString(res));
    }

    public int[] getFinalState(int[] nums, int k, int multiplier) {
        if(multiplier==1){
            return nums;
        }
        int maxNum = 0;
        PriorityQueue<long[]> heap = new PriorityQueue<>(new Comparator<long[]>() {
            @Override
            public int compare(long[] o1, long[] o2) {
                return (int) (o1[0] - o2[0] == 0 ? o1[1] - o2[1] : o1[0] - o2[0]);
            }
        });
        for (int i = 0; i < nums.length; i++) {
            maxNum = Math.max(maxNum, nums[i]);
            heap.offer(new long[]{nums[i], i});
        }
        while (heap.peek()[0] * multiplier <= maxNum && k > 0) {
            long[] poll = heap.poll();
            poll[0] *= multiplier;
            heap.offer(poll);
            k--;
        }
        int mod = 1000000007;
        int divisor = k / nums.length;
        long res = 1;
        long multiplierTemp = multiplier;
        while (divisor > 0) {
            if (divisor % 2 == 1) {
                res = res * multiplierTemp % mod;
            }
            multiplierTemp = multiplierTemp * multiplierTemp % mod;  // 将 multiplier 自身平方
            divisor /= 2;
        }
        int remainder = k % nums.length;
        for (int i = 0; i < nums.length; i++) {
            long[] poll = heap.poll();
            long product = poll[0] * res % mod;
            if (i < remainder) {
                product *= multiplier;
            }
            nums[(int) poll[1]] = (int) (product % mod);
        }
        return nums;
    }
}
